/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package huffman;

import java.util.*;
public class Driver {
    
    /**
     * @param args the command line arguments
     */
    
    public static void main(String args[])
    {
    // read System.in one character at a time
    Scanner s = new Scanner(System.in).useDelimiter("");
    SinglyLinkedList freq = new SinglyLinkedList();
    while (s.hasNext())
    {
    // s.next() returns string; we're interested in first char
    char c = s.next().charAt(0);
    if (c=='\n') break;
    // look up character in frequency list
    Leaf query = new Leaf(c);
    Leaf item = (Leaf)freq.remove(query);
    if (item == null)
    { // not found, add new Leaf
    freq.addFirst(query);
    } else { // found, increment Leaf
    item.frequency++;
    freq.addFirst(item);
    }
    }
    Iterator comida=freq.iterator();
    PriorityVector trees = new PriorityVector();  
    while(comida.hasNext()){
        trees.add(new HuffmanTree((Leaf)comida.next()));
    }
// read data from input   
      
    // merge trees in pairs until one remains
    while (trees.size() > 1)
    {
    // grab two smallest values
    HuffmanTree smallest = (HuffmanTree)trees.remove();
    HuffmanTree small = (HuffmanTree)trees.remove();
    // add bigger tree containing both
    trees.add(new HuffmanTree(smallest,small));
    }
    HuffmanTree encoding = (HuffmanTree)trees.remove();
    encoding.print();
    }
    
}

